package com.leetcode.search;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2019/10/14
 * @description: 34. 在排序数组中查找元素的第一个和最后一个位置
 * B
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * <p>
 * 如果数组中不存在目标值，返回 [-1, -1]。
 * <p>
 * 示例 1:
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 示例 2:
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SearchRange {

	/**
	 * 1.二分查找找到相等的值；
	 * 2.然后查找边界。
	 * 但是！
	 * 这样的时间复杂度是O(n+logn)
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int[] searchRange(int[] nums, int target) {
		int left = 0, right = nums.length, mid = 0;
		int[] ans = new int[2];
		boolean isFind = false;
		///1.判断临界情况
		if (nums.length == 1 && nums[0] == target) {
			isFind = true;
		}
		while (left < right) {
			mid = left + (right - left) / 2;
			if (nums[mid] == target) {
				isFind = true;
				break;
			}
			///跳出循环
			if (mid == left) {
				break;
			}
			if (nums[mid] < target) {
				left = mid;
			} else if (nums[mid] > target) {
				right = mid;
			}
//			else {
//				isFind = true;
//				break;
//			}
		}

		if (isFind) {
			///两次单指针判断范围
			left = right = mid;
			while (left > 0 && nums[left - 1] == target) {
				left--;
			}
			while (right + 1 < nums.length && nums[right + 1] == target) {
				right++;
			}
			ans[0] = left;
			ans[1] = right;


		} else {
			ans[0] = -1;
			ans[1] = -1;
		}
		return ans;
	}

	/**
	 * 为了确切达到时间复杂度O(logn)
	 * 1.二分查找寻找左索引；
	 * 2.二分查找寻找右索引；
	 * 时间复杂度O(2logn)=时间复杂度O(logn)
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int[] searchRangeRightComplexity(int[] nums, int target) {
		int left = 0, right = nums.length, mid = 0;
		int preLeft = 0, preRight = right;
		int[] ans = new int[2];
		boolean isFind = false;
		if (nums.length == 1 && nums[0] == target) {
			isFind = true;

		}
		while (left < right) {
			mid = left + (right - left) / 2;
			if (nums[mid] == target) {
				isFind = true;
				break;
			}
			///跳出循环
			if (mid == left) {
				break;
			}
			if (nums[mid] < target) {
				preLeft = left;
				left = mid;
			} else if (nums[mid] > target) {
				preRight = right;
				right = mid;
			}
		}

		/**
		 * 二分查找解决方法
		 */
		if (isFind) {
			///通过preLeft 和 preRight 继续二分查找左索引和右索引
			left = right = mid;
			while (preLeft < left) {
				int mid2 = preLeft + (left - preLeft) / 2;
				if (nums[mid2] == target) {
					if (left==mid2){
						break;
					}
					left = mid2;
				} else {
					if (preLeft==mid2){
						break;
					}
					preLeft=mid2;
				}
			}
			ans[0] = left;
			while (right < preRight) {
				int mid2 = right + (preRight - right) / 2;
				if (nums[mid2] == target) {
					if (right==mid2){
						break;
					}
					right = mid2;
				} else {
					if (preRight==mid2){
						break;
					}
					preRight=mid2;
				}
			}
			ans[1] = right;
		} else {
			ans[0] = -1;
			ans[1] = -1;
		}
		return ans;
	}

	public static void main(String[] args) {
		int[] nums = new int[]{1, 3};
		nums = new int[]{2, 2};
		nums=new int[]{1,2,3,3,3,3,4,5,9};
		///int[] ans = searchRange(nums, 2);
		int[] ans = searchRangeRightComplexity(nums, 3);
		System.out.println(Arrays.toString(ans));


	}
}
